#include <sys/types.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <dirent.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>
#include <string.h>

static int countDirs,countFiles,countHidden;
static char MAGIC[] = {'H','1','d','e'};
typedef unsigned char byte;

typedef struct q Q;
struct q {
	char *dir_name;
	Q *next;
};

Q *qhead, *qtail;
static int elements;

void q_init() {
	qhead = NULL;
	qtail = NULL;
	elements = 0;
}

int q_empty() {
	if(elements > 0) {
		return 0; //False -- q is not empty
	}
	return 1; //True -- q is empty.
}

void q_add(char *dir) {
	Q *new_node = (Q*)malloc(sizeof(Q));
	new_node->dir_name = (char*)malloc(strlen(dir)*sizeof(char)+1);
	strcpy(new_node->dir_name, dir);
	new_node->next = NULL;

	if(qhead == NULL) {
		qhead = new_node;
		qtail = new_node;
	}
	else {
		qtail->next = new_node;
		qtail = new_node;
	}	
	elements++;
}


char* q_get() {
	Q *node = qhead;
	char *filename = (char *)malloc(strlen(node->dir_name)*sizeof(char)+1);
	strcpy(filename, node->dir_name);
	if(qhead == qtail) {
		qhead = NULL;
	}
	else {
		qhead = qhead->next;
	}
	free(node->dir_name);
	free(node);
	elements --;
	return filename;
}

void usage(char*name) {
	fprintf(stderr,"Usage:\n%s directory\n",name);
	fprintf(stderr,"Recursive search for hidden data\n");
	exit(1);
}

void printSummary() {
	fprintf(stdout,"Search complete.\n%d directories examined, %d files examined, %d hidden files.\n",
		countDirs,countFiles,countHidden);	
}

void exitError(char*file,char *action) {
	perror("Exiting");
	fprintf(stderr,"Error while %s on %s.\n",action,file);
	exit(3);	
}

int isDirectory (char *path) {
	struct stat statbuf;
	if(stat(path, &statbuf) == -1) {
		exit(3);
	}
	else return (S_ISDIR(statbuf.st_mode));
}

int bfs () {
	DIR *dirp;
	struct dirent *direntp;
	char* file_name, tmp[1000];
   int ret = 0;

	while(!q_empty()) {
		if(isDirectory(file_name = q_get())) {
			if((dirp = opendir(file_name)) == NULL) {
				exitError(file_name, "opening");
			}
			countDirs++;
			while((direntp = readdir(dirp)) != NULL) {
				if(strcmp(direntp->d_name,".") && strcmp(direntp->d_name,"..")) {
					strcpy(tmp, file_name);
					int len = strlen(tmp);
					if(tmp[len-1] != '/') {
						strcat(tmp, "/");
					}
					strcat(tmp, direntp->d_name);
					q_add(tmp);
					if( !isDirectory(tmp) ) {
						countFiles++;
						int file;
						byte buffer[4096];
						byte integer[4];
						file = open (tmp, O_RDWR | O_APPEND);
						if( file == -1 ) {
                     break;
						}
						off_t offset = lseek (file, -4, SEEK_END);
						if( offset == -1 ) {
                     break;
						}
						ssize_t num_bytes = read ( file, (void* ) buffer, 4);
						if(num_bytes >= 4) {
							if( (buffer[0] == MAGIC[0]) && (buffer[1] == MAGIC[1]) && (buffer[2] == MAGIC[2]) && (buffer[3] == MAGIC[3])) {
								offset = lseek (file, -8, SEEK_END);
								if(offset == -1) {
                           break;
								}
								num_bytes = read(file, (void*)integer, 4);
								int i = 0;
								long length = *((long*)integer);
								for( i = 0; i < 4; i++) {
									if(!(integer[i] < '9' && integer[i] > '0')){ //if length of file is not in numbers
                              ret = 2;
									}
                        }
								if(length >= 0) {
									printf("%s\n", tmp);
									countHidden++;
								}
								else if(length < 0) {
                           ret = 2;
								}
							}
						}
					}
				}
			}
			while((closedir(dirp) == -1) && (errno == EINTR));
		}
	}
   if(countHidden == 0) {
      ret = 2;
   }
   return ret;
}


int main(int argc, char** argv) {
	if(argc != 2) usage(argv[0]);
	q_init();
	countDirs = 0; countFiles = 0; countHidden = 0;
	q_add(argv[1]);
	int ret = bfs();
	printSummary();
	return 0;	
}

